#include <algorithm>
#include <assert.h>
#include <iostream>
#include <list>
using namespace std;

namespace zzy
{
    template<class T>
    struct list_node
    {
        list_node<T>* _next;
        list_node<T>* _prev;
        T _val;

        explicit list_node(const T& val = T())
            :_next(nullptr)
            ,_prev(nullptr)
            ,_val(val)
        {}
    };

    template<class T, class Ref = T&, class Ptr>
    struct _list_iterator
    {
        typedef list_node<T> Node;
        typedef _list_iterator<T, Ref, Ptr> self;
        Node* _node;

        explicit _list_iterator(Node* node)
            :_node(node)
        {}

        Ref operator*() const
        {
            return _node->_val;
        }

        self& operator++()
        {
            _node = _node->_next;
            return *this;
        }

        self operator++(int)
        {
            self tmp = *this;
            _node = _node->_next;
            return tmp;
        }

        bool operator!=(const self& it) const
        {
            return _node != it._node;
        }

        Ptr operator->() const
        {
            return &_node->_val;
        }

        self& operator--()
        {
            _node = _node->_prev;
            return *this;
        }
        self operator--(int)
        {
            self tmp = *this;
            _node = _node->_prev;
            return tmp;
        }
    };

    template<class T>
    class list
    {
        typedef list_node<T> Node;

    public:
        typedef _list_iterator<T, T&, T*> iterator;
        typedef _list_iterator<T, const T&, const T*> const_iterator;

        iterator begin()
        {
            return iterator(_head->_next);
        }
        iterator end()
        {
            return iterator(_head);
        }

        list()
        {
            _head = new Node;
            _head->_prev = _head;
            _head->_next = _head;
            _size = 0;
        }

        void push_back(const T& x)
        {
            Node* tail = _head->_prev;
            Node* newnode = new Node(x);

            tail->_next = newnode;
            newnode->_prev = tail;

            newnode->_next = _head;
            _head->_prev = newnode;
        }

        iterator insert(iterator pos, const T& x)
        {
            Node* cur = pos._node;
            Node* prev = cur->_prev;
            Node* newnode = new Node(x);

            prev->_next = newnode;
            newnode->_next = cur;

            cur->_prev = newnode;
            newnode->_prev = prev;
            ++size;
            return newnode;
        }

        iterator erase(iterator pos)
        {
            assert(pos != end());

            Node* cur = pos._node;
            Node* prev = cur->_prev;
            Node* next = cur->_next;

            prev->_next = next;
            next->_prev = prev;

            delete cur;
            --size;
            return next;
        }

        void clear()
        {
            iterator it = begin();
            while (it != end())
            {
                it = erase(it);
            }
            _size = 0;
        }

        size_t size() const
        {
            return _size;
        }

        ~list()
        {
            clear();
            delete _head;
            _head = nullptr;
        }

        list(const list<T>& lt)
        {
            _head = new Node;
            _head->_prev = _head;
            _head->_next = _head;

            _size = 0;

            for(auto& e : lt)
            {
                push_back(e);
            }
        }

        void swap(list<T>& lt)
        {
            std::swap(_head, lt._head);
            std::swap(_size, lt._size);
        }

        list<T>& operator=(const list<T>& lt)
        {
            swap(lt);

            return *this;
        }
    private:
        Node* _head;
        size_t _size;
    };
}

// void test_list()
// {
//     list<A> lt;
//     lt.push_back(A(1));
//     lt.push_back(A(2));
//     lt.push_back(A(3));
//
//     list<A>::iterator it = lt.begin();
//     while (it != lt.end())
//     {
//         cout << (*it)._a << endl;
//         cout << it->_val._a << endl;
//         ++it;
//     }
//     cout << endl;
// }

